
/**
 * 1.如何将一个乱序的数构建成为一颗查找二叉树
 * 2.演示二叉查找树的遍历（前序 中序 后序）
 * 3.计算一颗二叉树的高度
 * 4.寻找一个非查找二叉树的最大值
 */
public class ErchaTree {
    public static void main(String[] args) {
        // 在本次所有案例中，不考虑重复的情况
        int[] arr = {4, 3, 5, 6, 8, 2, 9, 15, 13};
        // 创建树
        Tree tree = new Tree();
        // 构建查找二叉树
        for (int i = 0; i < arr.length; i++) {
            insetBinaryTree(tree, arr[i]);
        }
        // 前序遍历
//        preOrder(tree.getRoot());
        // 中序遍历
        inOrder(tree.getRoot());
        // 后序遍历
//        afterOder(tree.getRoot());
        // 获取树的高度
        int treeHeight = getHeight(tree.getRoot());
        System.out.println();
        System.out.println("树的高度为： " + treeHeight);
        // 获取无序非查找树的最大值
        int maxNum = getMaxNum(tree.getRoot());
        System.out.println("该二叉树的最大值为：" + maxNum);
    }

    private static int getMaxNum(Node node) {
        // 当节点为空是说明不存在，返回-1
        if (node == null) {
            return -1;
        }
        /**
         * 递归思路是这样的：
         *      假设，左边最大的值是 maxLeft, 中间根的值是mid, 右边最大的值是maxRright
         *      应当将这三个值做比较，获取最大的值返回
         */
        // 获取左子树的最大值
        int maxLeft = getMaxNum(node.getLeft());
        int mid = node.getData();
        int maxRight = getMaxNum(node.getRight());
        int maxVal = maxLeft;
        if (mid > maxLeft) {
            maxVal = mid;
        }
        if (maxRight > maxVal) {
            maxVal = maxRight;
        }
        return maxVal;
    }

    /**
     * 获取树的高度
     *
     * @param node
     * @return
     */
    private static int getHeight(Node node) {
        // 递归的出口
        if (node == null) {
            return 0;
        }
        /**
         * 树的高度应该左子树的高度与右字树的高度比较，选取最大的那个高度
         */
        // 获取左边树的高度
        int leftHeight = getHeight(node.getLeft());
        // 获取右边树的高度
        int rightHeight = getHeight(node.getRight());
        int maxHeight = leftHeight;
        // 左边树高和右边树高比较
        if (leftHeight < rightHeight) {
            maxHeight = rightHeight;
        }
        // 获取到最大的子树高度后，还要加上自己当前层的高度
        return maxHeight + 1;
    }

    /**
     * 后序遍历
     * 左 右 根
     *
     * @param node
     */
    private static void afterOder(Node node) {
        // 递归的出口，最后一层的后一层或者根节点是空的时候直接返回
        if (node == null) {
            return;
        }
        afterOder(node.getLeft());
        afterOder(node.getRight());
        System.out.print(node.getData() + "\t");
    }

    /**
     * 中序遍历
     * 左  根  右    它一定是从小到大的顺序
     *
     * @param node
     */
    private static void inOrder(Node node) {
        // 递归的出口，最后一层的后一层或者根节点是空的时候直接返回
        if (node == null) {
            return;
        }
        // 先中序遍历左节点
        inOrder(node.getLeft());
        // 输出中间节点
        System.out.print(node.getData() + "\t");
        // 中序遍历右节点
        inOrder(node.getRight());
    }

    /**
     * 树的前序遍历
     * 根  左  右    的顺序
     *
     * @param node
     */
    private static void preOrder(Node node) {
        // 递归的出口，最后一层的后一层或者根节点是空的时候直接返回
        if (node == null) {
            return;
        }
        // 先输出根节点
        System.out.print(node.getData() + "\t");
        // 前序遍历左字树
        preOrder(node.getLeft());
        // 前序遍历右字树
        preOrder(node.getRight());
    }

    /**
     * 将传进来来的值插入树中，形成一颗查找二叉树
     *
     * @param tree
     * @param value
     */
    private static void insetBinaryTree(Tree tree, int value) {
        Node temp = tree.getRoot();
        // 假如是第一次，也就是个空树的情况
        if (temp == null) {
            temp = new Node();
            // 直接给根节点赋值退出即可
            temp.setData(value);
            tree.setRoot(temp);
            return;
        }
        // 数据一定是要插入到空节点上，所以需要循环判断
        while (temp != null) {
            /**
             * 假如比当前节点的值要小，就需要判断左孩子是否为空，
             * 如果为空直接插入到左孩子节点即可
             * 如果不为空，则将temp赋值为做孩子节点，进行下轮的比较
             */
            if (value < temp.getData()) {
                // 获取当前节点的左孩子
                Node left = temp.getLeft();
                // 将左孩子插入到父节点这里是temp下,如果成功了就退出方法，否则继续比较
                if (left == null) {
                    left = new Node();
                    left.setData(value);
                    temp.setLeft(left);
                    return;
                } else {
                    temp = left;
                }
            } else { // 这个值比当前节点的值大的情况，与上述情况相反
                Node right = temp.getRight();
                if (right == null) {
                    right = new Node();
                    right.setData(value);
                    temp.setRight(right);
                    return;
                } else {
                    temp = right;
                }
            }
        }
    }
}

/**
 * 声明一个节点对象，它必然有自己保存的数据，左孩子和右孩子
 */
class Node {
    // 当前节点保存的值
    private int data;
    // 左孩子
    private Node left;
    // 右孩子
    private Node right;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

/**
 * 声明一个树，它代表了这颗二叉树，并且只有一个根节点即可，因为数就是个链表结构
 */
class Tree {
    // 树的根节点，下面会连接为一颗参天大树
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
}

